As used herein, “/” denotes alternative names for the same or similar components or structures. That is, a “/” can be taken as meaning “or” as used herein. Unicast transmissions are between a single sender/transmitter and a single receiver. Broadcast transmissions are between a single sender/transmitter and all receivers within receiving range of the transmitter. Multicast transmissions are between a single sender/transmitter and a subset of the receivers within receiving range of the transmitter where the subset of receivers with receiving range of the transmitter may be the entire set. That is, multicast may include broadcast and is therefore a broader term than broadcast as used herein. Data/content is transmitted in packets or frames. As used herein a station can be a node or a client device, which can be a mobile terminal or mobile device such as, but not limited to, a computer, laptop, personal digital assistant (PDA) or dual mode smart phone.
The popularity of voice and video applications over mobile computing devices has raised concerns regarding the performance of medium access control (MAC) protocols, which are responsible for allocating shared medium resources to multiple communicating stations and resolving collisions that occur when two or more stations access the medium simultaneously. In the current IEEE 802.11 wireless LANs, the distributed coordination function (DCF) of the MAC protocol layer uses a binary exponential back-off (BEB) algorithm for fundamental channel access. The BEB algorithm mitigates the issue of network collisions by randomizing the timing of medium access among stations that share the communication medium. However, as demonstrated by both practical experience and theoretical analysis, the BEB algorithm has some deficiencies. First, the collision probability for a transmission attempt increases exponentially with the number of active stations in the network, which significantly impairs the network throughput for large-scale networks. Second, the medium access delay cannot be bounded and the jitter is variable, which may not be suitable for multimedia applications. Third, the opportunity for medium access is not fair among stations. That is, a given station may gain access to the communication medium and get served for a long time. This results in other stations having to greatly defer their access to the medium. Moreover, it turns out that the use of doubling the contention window upon failed transmissions appears to give more transmission opportunities to these successful stations.
The concept of reducing or eliminating contention in contention-based networks was introduced by the present Applicants using a form of round robin scheduling in an earlier patent applications PCT Application Serial Numbers PCT/US2007/014607 and PCT/US2007/014608. This concept works well in contention-based networks where there is a centralized controller or coordinator, which can be the global repository of knowledge and equally importantly disseminate and distribute that global knowledge in order to coordinate the activities of the nodes or stations of the network.
To overcome the above-identified problems, an alternative back-off method—relaxed DEB (R-DEB) was described in EPO Application No. 08300154.5-2416. The R-DEB method improved the DEB algorithm in two ways. First, the R-DEB method fixed the back-off window to a predefined value. Second, the R-DEB method changed the frame transmission triggering condition by permitting multiple transmission opportunities when the back-off slot counters counted down from a maximum to a minimum. Randomization was introduced in the R-DEB algorithm during the selection of the triggering set. This enhanced its robustness against physical sensing error and increased the management flexibility, at the cost of a slight degradation of network efficiency. The R-DEB method was backward compatible with legacy IEEE 802.11 standards. Frames and packets are units of data. That is, data can be packaged in packets or frames or any other convenient format. As used herein a frame is used to indicate data/content packaged in a format for transmission.
In EPO Application No. 08300154.5-2416, the R-DEB method was introduced to overcome issues such as backward compatibility and dependability that were raised for the DEB algorithm. The R-DEB selected the back-off slot count in as deterministic a way as possible to avoid network collisions, and also R-DEB introduced randomness to the procedure to preserve the flexibility and ease of deployment which is a feature of random back-off algorithms such as BEB (binary exponential back-off). Hence, R-DEB made a compromise between the network efficiency and flexibility, and can be viewed as a combination of the DEB algorithm and BEB algorithm. The initial motivation of the R-DEB algorithm was to adapt the deterministic back-off for video transport systems while maintaining backward compatibility with the previous standards.
The R-DEB operates as follows. A back-off round starts when a station resets its back-off slot count slot(n) to the fixed number M (note that here n is a variable on the timeline). Once a station/node/client determines by the physical carrier sensing procedure that the shared medium is idle for a time slot, the station/node/client decreases its back-off slot count by one. If this new slot count satisfies the transmission triggering event/condition, or in other words the slot count is equal to one of the elements of the triggering set QT, e.g., slot(n)=k, then the station/node/client will get an opportunity to initiate a data transmission (hence “triggering a transmission”). If no frame is to be sent at this time, the station/node/client forgoes the opportunity and continues decreasing its slot count. The result of the transmission determines whether or not the element k should remain in the triggering set. A successful transmission allows this element remain in the triggering set, while an unsuccessful transmission will, with a probability p, trigger an element substitution procedure that replaces the old element k with a new element k′ from the interval [0, M]. As the choice of k′ may affect the performance of R-DEB, it is clear that a proper selection method should be designed to select k′ as the new element for insertion into the triggering set QT. In EPO Application No. 08300154.5-2416, a random selection method was described to select k.
The random selection method included two main parts, random selection for each selecting attempt and p-persistent back-off upon failed transmission attempts. Each time that a station wanted to select and insert a new element from interval [0, M] into its triggering set QT, the station randomly selected a value from the integers available in the interval [0, M] that were currently not in its triggering set QT. Alternatively, a station maintained a history of past selections and the results of those selections. A station using this latter method would select those values that had fewer unsuccessful transmission attempts. For example, if during a recent period when selecting the value k as an element of the QT, the station encountered more network collisions than other choices, then the station will re-select k as a triggering element/value with a low probability. Hence, a table, histogram, matrix or other means could have been maintained for each integer from 0 to M along with the number of failed transmissions during the past period T when using this integer as a transmission trigger. The station would then select an integer with such a probability that it was negative proportional to the number of failed attempts during the past period T. For example, if r(k) denotes the record for integer k, then the station would select k as a new element of QT with a probability qk computed by,
                              q          k                =                              r            ⁡                          (              k              )                                                          ∑                              j                ∈                                  Q                  T                                                      ⁢                                                  ⁢                          r              ⁡                              (                j                )                                                                        (        1        )            
The p-persistent back-off mechanism was based on the case of an unsuccessful frame transmission. The station deleted the corresponding element k from the triggering set QT with a predefined probability p and a new element had to be selected for insertion into the trigger set to makeup for the deleted element using the above described random selection method. This procedure continues persistently until an appropriate element was selected that yielded a successful transmission.
In the random selection method, a candidate integer in [0, M] was selected for insertion into the triggering set based on the history of transmission results when using that integer for transmission trigger during a past period. This approach is simple and easy to implement, since the information used for the selection decision was limited to local transmission records. In this sense the R-DEB method achieved completely distributed deterministic back-off for multiple access in wireless LANs (note that the original DEB algorithm relied on the central coordinator to disseminate/update the global information for each station). However, restricting the selection procedure to local information increases the possibility of network collisions. Specifically, if the two elements selected by station A and station B correspond to the same time slot on the time line of the shared medium, then the two stations would collide with each other when both use the two elements for medium access.